In some conventional laser printers generally available today, the architecture of the hardware and software operating systems is such that the bitmap page image is divided up into a checkerboard pattern of units called "blocks." The number of blocks per page is dependent upon the paper size, block size, printhead resolution in dpi (dots per inch), and bitmap resolution in bits/pel. For example, an 8 1/2".times.11" page can be divided into rectangular blocks in which there are twenty (20) horizontal blocks .times. one hundred (100) vertical blocks on the page. At a printhead resolution of 1200 dpi and bitmap resolution of one bit/pel, each block would be 512 pels wide .times.128 pels high.
Typically, the size of random access memory (RAM) in the printer is less than that required to store a full page bitmap. Hence, memory is allocated on a block basis when information is "painted" into each block by the rasterization process. Therefore, each block of bitmap image data is stored in a separate area from the other similar blocks, and these smaller areas will quite likely to be spread all over different memory address locations of the printer's RAM. However, when the bitmap image is to be printed, a transformation of the data stored in RAM must occur in conventional printers from a "scattered" block page representation to a "gathered" banded page representation, in which a "band" comprises a group of horizontal blocks that extend across the entire width of the printed page. This band building process copies the non-contiguous blocks into "band buffers" which each hold a page width strip in contiguous memory.
Depending upon the printer's throughput (i.e., pages per minute), multiple bands must be buffered before the image can be printed. In many printers, a specific set of memory locations is reserved in the printer's main RAM system to hold these multiple bands. A minimum of two bands is typically stored in the system's RAM: (1) the band that is presently being sent to the laser printhead as a serial data stream, and (2) another band that is currently being built so that it will be completed (and ready to print) before the previous band has finished being printed.
Some of the fundamental problems for the back end rendering software in conventional printers is that the band building process involves a copying operation of bitmap image data from the scattered blocks in non-contiguous RAM locations into the pre-allocated contiguous memory locations in RAM used to store the band buffer in real time (while the paper is moving through the printer), and thereby requiring a portion of the main processor's performance. In addition, null or "blank" blocks must be copied into the band buffer just like "real data" blocks, thereby requiring memory retrieval and storage operations that take up memory bandwidth (i.e., requiring access time to use the memory system's address and data busses). Furthermore, additional RAM locations must be allocated to hold the null block image data in the non-contiguous blocks, and additional memory must be allocated to hold the multiple band buffers.
Some of the patents which disclose image building systems for printers are as follows: U.S. Pat. No. 4,942,541 (by Hoel) discloses a patchification system that uses virtual memory for mapping image data in a printer. Physical memory is allocated as "patches" and the physical memory is used in creating a page image bitmap. A patch corresponds to a rectangular area of the page in bitmap form, and each patch is represented by non-contiguous segments of the virtual (or logical) memory, which when later mapped to the physical memory, are contiguous. When a "blank" patch is found during the step of allocation of physical memory, the blank patch is mapped to a single "blank" physical patch. All such blank patches are mapped to this same single blank physical patch. During printing, the blank physical patch is mapped back into the correct blank areas of the logical page image. This occurs during a serialization process, and if a particular mapped physical patch was found to be a zero patch, then the single blank physical patch in memory is accessed to ship the correct blank data (for the blank logical patch) to the printer. The non-blank data is mapped to physical memory addresses using logical patchified addresses, in which the physical addresses can be non-contiguous. When it is time to ship the data to the printer, the logical addresses which are contiguous use an offset (or pointer) to find the correct physical addresses to provide the proper data, as needed for the printer. This includes both blank and non-blank data as the individual patches of data are needed for the printer.
U.S. Pat. No. 5,502,804 (by Butterfield) discloses a laser printer that generates output page images in real time. Rather than requiring an entire page to be built in a bitmap form before sending it to the print engine, Butterfield discloses the use of building a single band to begin the process of printing, and after building the first band, a second band is created while the first band is being printed. By use of this method, a good deal of memory can be saved since an entire bitmap page need not be constructed before sending the data to a print engine. Even if sufficient memory is available to build a complete page, by using the banding technique of Butterfield a second page can be constructed in one band while a first page in another band is being printed. Butterfield receives high language level print job data and converts this data to "graphics orders" rather than converting directly to bitmaps. Since a single graphics command may affect more than one band, an order may be processed multiple times, using "command blocks" that are tabular structures in memory. An "order construction step" is first performed, and attempts to eliminates redundant orders by combining multiple inputs into single command blocks (thereby minimizing memory).
A first (intermediate) image drawing step proceeds in parallel with the order construction step, and draws objects in the page image. The objects are stored in the user memory for use as source data for the next (or second) drawing step. The second (deferred) image drawing step begins when all of the orders for the page image have been generated. This step may process order commands multiple times, one for each image band affected.
U.S. Pat. No. 5,574,953 (by Rust) discloses a data compression and decompression system that stores compressed data in non-contiguous memory. As the data is compressed and stored in memory, the non-contiguous segments are marked, by placing a pointer at the last location that points to the next memory used. Just prior to the pointer, a special "link" code is stored, which logically links together the non-contiguous memory. When the data is decompressed, if the code is a link code, then the address pointer directs the system to the next location in memory where the next compressed data is stored to retrieve that segment. If the code is not a link code, then the code (or data) is decompressed.
U.S. Pat. No. 5,129,088 (by Auslander) discloses a data processing system that creates virtual disks from non-contiguous groups of blocks on hard disk drives. Each drive (or drives) of physical memory locations is divided into physical partitions, each partition comprising a predetermined number of contiguous addressable blocks. The partitions in each group of blocks are not necessarily physically contiguous, although the "logical" blocks are contiguous. As the system memory requires further locations to be allocated, the system can automatically allocate one or more additional partitions, and this occurs dynamically to store further information.
U.S. Pat. No. 4,555,802 (by Fedak) discloses a system that divides image data into a plurality of segments in which each segment is either square or rectangular. The segments are analyzed to determine which contain blank or zero data or which contain at least one bit of non-zero data. The blank segments are ignored and the non-blank segments are stored and indexed. A directory is created to indicate the storage location of each group of non-blank segments as well as their spatial location with respect to the rectangular raster array of signals. All compaction and decompaction machine operations are independent of bit-significant informational content of the segments.
U.S. Pat. No. 5,416,615 (by Shirota) discloses a digital data transmitting device that extracts image data in both horizontal and vertical directions and forms an "original block" of n .times.n pixel data. From this information, a transformation operation is performed, such as a two-dimensional cosine transform, thereby creating a "differential block" that consists of m .times.m pixel data. The differential block data is "transform coded" to generate "coefficient data", and a "flag generation circuit" is used to transmit the coefficient data. However, this flag generation circuit generates a flag if there is an omission of the transmission of coefficient data when there is no meaningful data (generally meaning blank data), and a separate transmission circuit will transmit the flag or flags and the pixel data of blocks.
In conventional printers of the prior art, a "band" of rasterized bitmap image data must be constructed in contiguous memory before sending the band as serial data to the laser print engine. In fact, in most conventional printers, two separate bands have specific locations reserved in random access memory, one set of contiguous memory locations for the band that is now being output to the laser printhead, and a second set of contiguous memory locations for the band that is now being built. By the time the first band's data has been completely sent to the laser printhead, the second band will be entirely completed in contiguous memory, and will be available to send to the laser printhead as needed.
The amount of random access memory (RAM) reserved for the band building process is not insignificant. For example, at 1200 dpi (dots per inch) resolution, a band that covers an 8 1/2" wide page, and contains 128 horizontal raster lines will require 160 Kbytes of memory. For holding two bands (or at least reserving space in memory for two such bands), the printer's memory must reserve 320 Kbytes of space.
Since many laser printers are manufactured having 2 Mbytes of RAM, this 320 KB requirement is a significant portion of the entire printer's memory. If it were possible to eliminate the memory requirements for the band building process, then a significant savings in memory space and in memory bandwidth could be realized as a significant commercial advantage, and also a performance savings for the printer.